package jzoffer;

import leetcode.tree.TreeNode;

import java.util.HashMap;
import java.util.Map;

/**
 * @author wangmaolin1
 * @date 2021/12/5 下午5:15
 */
public class _07重建二叉树 {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder == null || preorder.length == 0) {
            return null;
        }
        Map<Integer, Integer> inorderMap = new HashMap<>(inorder.length);
        for (int i = 0; i < inorder.length; i++) {
            inorderMap.put(inorder[i],i);
        }
        return build(inorderMap,preorder,0,preorder.length-1, 0);

    }

    /**
     * 前提知识： 前序遍历，第一个就是根节点
     * 根节点的左孩子就是下一个节点；
     * 根节点的右孩子的位置=当前root位置+root 的左子树节点数量+1；
     * 由前序遍历的根节点，可在中序遍历中找到根节点所在位置rootIndex，该位置左边的为 root 的左子树节点，右边的为 root 的右子树节点
     * 因此 root左子树节点数量= rootIndex-inorderStart
     * @param inorderMap key:中序遍历值  value：中序遍历索引
     * @param pStart 当前递归节点前序遍历左边界，即，就是当前子树的根节点位置
     * @param pEnd  前序右边界
     * @param inStart 中序遍历左边界
     * @return
     */
    private TreeNode build(Map<Integer, Integer> inorderMap, int[] preorder, int pStart, int pEnd, int inStart) {
        if (pStart>pEnd){
            return null;
        }
        //当前根节点在中序遍历中的索引
        Integer rootIndex = inorderMap.get(preorder[pStart]);
        // 根节点位置-左子树开始位置=根节点左孩子的节点数量
        int leftCount=rootIndex-inStart;
        TreeNode root=new TreeNode(preorder[pStart]);
        //左孩子作为 root 节点时，其位置为 pStart+1，，左孩子所有节点起始位置依然是 inStart
        root.left=build(inorderMap,preorder,pStart+1,pStart+leftCount, inStart);
        //右孩子作为 root 节点时，其位置为 pStart+leftCount+1，右孩子的所有节点从 rootIndex+1 开始
        root.right=build(inorderMap,preorder,pStart+leftCount+1,pEnd, rootIndex+1);
        return root;

    }

}
